package array;

/**
 * @author 陈正龙
 * @date 2022/3/3 13:05
 * 回溯算法
 */
public class _005 {


    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int r = board.length;
        int c = board[0].length;
        if (r * c < word.length()) {
            return false;
        }
        visited = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] grid, String word, int index, int r, int c) {
        if (index >= word.length()) {
            return true;
        }
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
            return false;
        }
        if (visited[r][c]) {
            return false;
        }
        if (grid[r][c] != word.charAt(index)) {
            return false;
        }
        visited[r][c] = true;
        boolean flag1 = dfs(grid, word, index + 1, r + 1, c);
        if (flag1) {
            return true;
        }
        boolean flag2 = dfs(grid, word, index + 1, r - 1, c);
        if (flag2) {
            return true;
        }
        boolean flag3 = dfs(grid, word, index + 1, r, c + 1);
        if (flag3) {
            return true;
        }
        boolean flag4 = dfs(grid, word, index + 1, r, c - 1);
        if (flag4) {
            return true;
        }
        visited[r][c] = false;
        return false;
    }

}
